package 链表;

public class 排序链表 {
    public static void main(String[] args) {
        ListNode first = new ListNode(4);
        first.next = new ListNode(2);
        first.next.next = new ListNode(1);
        first.next.next.next = new ListNode(3);

        排序链表 test = new 排序链表();
        first = test.sort(first);
        System.out.println(first);
    }


    public ListNode sortList(ListNode head) {
        ListNode h, h1, h2, pre, res;
        h = head;
        int length = 0, intv = 1;
        while (h != null) {
            h = h.next;
            length++;
        }
        res = new ListNode(0);
        res.next = head;
        while (intv < length) {
            pre = res;
            h = res.next;
            while (h != null) {
                int i = intv;
                h1 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                if (i > 0) break;
                i = intv;
                h2 = h;
                while (i > 0 && h != null) {
                    h = h.next;
                    i--;
                }
                int c1 = intv, c2 = intv - i;
                while (c1 > 0 && c2 > 0) {
                    if (h1.val < h2.val) {
                        pre.next = h1;
                        h1 = h1.next;
                        c1--;
                    } else {
                        pre.next = h2;
                        h2 = h2.next;
                        c2--;
                    }
                    pre = pre.next;
                }
                pre.next = c1 == 0 ? h2 : h1;
                while (c1 > 0 || c2 > 0) {
                    pre = pre.next;
                    c1--;
                    c2--;
                }
                pre.next = h;
            }
            intv *= 2;
        }
        return res.next;
    }

    private ListNode sort(ListNode node) {
        int val = node.val;
        ListNode centerNode = node;
        ListNode frontNode = null;
        ListNode afterNode = null;
        ListNode afterHead = null;
        ListNode frontHead = null;
        while (node.next != null) {
            node = node.next;
            if (node.val < val) {
                if (frontNode == null) {
                    frontHead = node;
                    frontNode = node;
                } else {
                    frontNode.next = node;
                    frontNode = node;
                }
            } else {
                if (afterNode == null) {
                    afterHead = node;
                    afterNode = node;
                } else {
                    afterNode.next = node;
                    afterNode = node;
                }
            }
        }
        if (frontNode != null) {
            frontNode.next = null;
        }
        if (afterNode != null) {
            afterNode.next = null;
        }

        if (frontHead != null) {
            frontHead = sort(frontHead);
            node = frontHead;
            while (node.next != null) {
                node = node.next;
            }
            node.next = centerNode;
        }
        if (afterHead != null) {
            afterHead = sort(afterHead);
            centerNode.next = afterHead;
        }

        if (frontHead != null) {
            return frontHead;
        } else {
            return centerNode;
        }


    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}


